package dp.waysToStep;
/**
 * @Date 2020/04/16
 * @author 王光浩
 * @Thinking 使用DP
 */
public class MyMethodTwo {
	public int waysToStep(int n) {
		if(n < 3)return n; 
		int[] cache = new int[3];
		cache[0] = 1;
		cache[1] = 1;
		cache[2] = 2;
		for(int i=3 ; i<=n ; i++) {
			int tem = ((cache[i-3]+cache[i-2])%1000000007+cache[i-1])%1000000007;
			cache[0] = cache[1];
			cache[1] = cache[2];
			cache[2] = tem;
			
		}
		return cache[2];
	}
}
